class Solution {
    static class TreeNode {
        int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    public int massage(int[] nums) {
        //1.创建dp表
        int m = nums.length;
        int[] dp = new int[m+3];
    
        //2.初始化
        dp[0] = dp[1] = dp[2] = 0;

        //3.填表
        for(int i = 3; i < m+3; i++) {
            dp[i] = Math.max(dp[i-2], dp[i-3]) + nums[i-3];
        }

        //4.返回值
        return Math.max(dp[m+2], dp[m+1]);
    }
    public TreeNode pruneTree(TreeNode root) {
        boolean rootTree = dfs(root);
        if(rootTree) return null;
        return root;
    }
    private boolean dfs(TreeNode root) {
        if(root == null) return true;
        boolean leftTree = dfs(root.left);
        if(leftTree) root.left = null;
        boolean rightTree = dfs(root.right);
        if(rightTree) root.right = null;
        return leftTree && rightTree && root.val == 0;
    }
    public TreeNode pruneTree2(TreeNode root) {
        if (root == null)
            return null;
        root.left = pruneTree2(root.left);
        root.right = pruneTree2(root.right);
        if (root.left == null && root.right == null && root.val == 0)
            root = null;
        return root;
    }
}